Parameterized Complexity of the Firefighter Problem
Identifieur interne : 006357 ( Main/Exploration ); précédent : 006356; suivant : 006358Parameterized Complexity of the Firefighter Problem
Auteurs : Cristina Bazgan [France] ; Morgan Chopin [France] ; Michael R. Fellows [Australie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
English descriptors
- KwdEn :
- Algorithm, Bipartite graphs, Busy gadget, Busy gadgets, Clique, Computable function, Cubic graphs, Discrete mathematics, Equivalent instance, Former problem, General graphs, Heidelberg, Input instance, Kernel, Maximum degree, Output instance, Parameter tractability, Parameterized, Parameterized complexity, Parameterized intractability, Parameterized problem, Parameterized problems, Planar graphs, Poly kernel, Polynomial kernel, Polynomial kernels, Polynomial time, Problem parameterized, Protection strategy, Reduction rule, Regular clique, Same number, Several cases, Subset, Time proof, Time step, Tractable, Valid strategy, Vertex, Vulnerable vertex.
- Teeft :
- Algorithm, Bipartite graphs, Busy gadget, Busy gadgets, Clique, Computable function, Cubic graphs, Discrete mathematics, Equivalent instance, Former problem, General graphs, Heidelberg, Input instance, Kernel, Maximum degree, Output instance, Parameter tractability, Parameterized, Parameterized complexity, Parameterized intractability, Parameterized problem, Parameterized problems, Planar graphs, Poly kernel, Polynomial kernel, Polynomial kernels, Polynomial time, Problem parameterized, Protection strategy, Reduction rule, Regular clique, Same number, Several cases, Subset, Time proof, Time step, Tractable, Valid strategy, Vertex, Vulnerable vertex.
Abstract
Abstract: In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that Saving k -Vertices and its dual Saving All But k -Vertices are both W[1]-hard for parameter k even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance, Saving k -Vertices is fixed-parameter tractable on planar graphs for parameter k. Moreover, we prove a lower bound to polynomial kernelization for Saving All But k -Vertices.
Url:
DOI: 10.1007/978-3-642-25591-5_66
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001518
- to stream Istex, to step Curation: 001518
- to stream Istex, to step Checkpoint: 000776
- to stream Main, to step Merge: 006733
- to stream Main, to step Curation: 006357
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Parameterized Complexity of the Firefighter Problem</title><author><name sortKey="Bazgan, Cristina" sort="Bazgan, Cristina" uniqKey="Bazgan C" first="Cristina" last="Bazgan">Cristina Bazgan</name></author><author><name sortKey="Chopin, Morgan" sort="Chopin, Morgan" uniqKey="Chopin M" first="Morgan" last="Chopin">Morgan Chopin</name></author><author><name sortKey="Fellows, Michael R" sort="Fellows, Michael R" uniqKey="Fellows M" first="Michael R." last="Fellows">Michael R. Fellows</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:70BD68B8E1DA56DBB7F6C3404A53D5FD25290EE3</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-25591-5_66</idno><idno type="url">https://api.istex.fr/document/70BD68B8E1DA56DBB7F6C3404A53D5FD25290EE3/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001518</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001518</idno><idno type="wicri:Area/Istex/Curation">001518</idno><idno type="wicri:Area/Istex/Checkpoint">000776</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000776</idno><idno type="wicri:doubleKey">0302-9743:2011:Bazgan C:parameterized:complexity:of</idno><idno type="wicri:Area/Main/Merge">006733</idno><idno type="wicri:Area/Main/Curation">006357</idno><idno type="wicri:Area/Main/Exploration">006357</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Parameterized Complexity of the Firefighter Problem</title><author><name sortKey="Bazgan, Cristina" sort="Bazgan, Cristina" uniqKey="Bazgan C" first="Cristina" last="Bazgan">Cristina Bazgan</name><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>LAMSADE, Université Paris-Dauphine</wicri:regionArea><wicri:noRegion>Université Paris-Dauphine</wicri:noRegion><wicri:noRegion>Université Paris-Dauphine</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>Institut Universitaire de France</wicri:regionArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Chopin, Morgan" sort="Chopin, Morgan" uniqKey="Chopin M" first="Morgan" last="Chopin">Morgan Chopin</name><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>LAMSADE, Université Paris-Dauphine</wicri:regionArea><wicri:noRegion>Université Paris-Dauphine</wicri:noRegion><wicri:noRegion>Université Paris-Dauphine</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Fellows, Michael R" sort="Fellows, Michael R" uniqKey="Fellows M" first="Michael R." last="Fellows">Michael R. Fellows</name><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>Charles Darwin University</wicri:regionArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Australie</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2011</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Bipartite graphs</term><term>Busy gadget</term><term>Busy gadgets</term><term>Clique</term><term>Computable function</term><term>Cubic graphs</term><term>Discrete mathematics</term><term>Equivalent instance</term><term>Former problem</term><term>General graphs</term><term>Heidelberg</term><term>Input instance</term><term>Kernel</term><term>Maximum degree</term><term>Output instance</term><term>Parameter tractability</term><term>Parameterized</term><term>Parameterized complexity</term><term>Parameterized intractability</term><term>Parameterized problem</term><term>Parameterized problems</term><term>Planar graphs</term><term>Poly kernel</term><term>Polynomial kernel</term><term>Polynomial kernels</term><term>Polynomial time</term><term>Problem parameterized</term><term>Protection strategy</term><term>Reduction rule</term><term>Regular clique</term><term>Same number</term><term>Several cases</term><term>Subset</term><term>Time proof</term><term>Time step</term><term>Tractable</term><term>Valid strategy</term><term>Vertex</term><term>Vulnerable vertex</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Bipartite graphs</term><term>Busy gadget</term><term>Busy gadgets</term><term>Clique</term><term>Computable function</term><term>Cubic graphs</term><term>Discrete mathematics</term><term>Equivalent instance</term><term>Former problem</term><term>General graphs</term><term>Heidelberg</term><term>Input instance</term><term>Kernel</term><term>Maximum degree</term><term>Output instance</term><term>Parameter tractability</term><term>Parameterized</term><term>Parameterized complexity</term><term>Parameterized intractability</term><term>Parameterized problem</term><term>Parameterized problems</term><term>Planar graphs</term><term>Poly kernel</term><term>Polynomial kernel</term><term>Polynomial kernels</term><term>Polynomial time</term><term>Problem parameterized</term><term>Protection strategy</term><term>Reduction rule</term><term>Regular clique</term><term>Same number</term><term>Several cases</term><term>Subset</term><term>Time proof</term><term>Time step</term><term>Tractable</term><term>Valid strategy</term><term>Vertex</term><term>Vulnerable vertex</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that Saving k -Vertices and its dual Saving All But k -Vertices are both W[1]-hard for parameter k even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance, Saving k -Vertices is fixed-parameter tractable on planar graphs for parameter k. Moreover, we prove a lower bound to polynomial kernelization for Saving All But k -Vertices.</div></front></TEI><affiliations><list><country><li>Australie</li><li>France</li></country></list><tree><country name="France"><noRegion><name sortKey="Bazgan, Cristina" sort="Bazgan, Cristina" uniqKey="Bazgan C" first="Cristina" last="Bazgan">Cristina Bazgan</name></noRegion><name sortKey="Bazgan, Cristina" sort="Bazgan, Cristina" uniqKey="Bazgan C" first="Cristina" last="Bazgan">Cristina Bazgan</name><name sortKey="Bazgan, Cristina" sort="Bazgan, Cristina" uniqKey="Bazgan C" first="Cristina" last="Bazgan">Cristina Bazgan</name><name sortKey="Chopin, Morgan" sort="Chopin, Morgan" uniqKey="Chopin M" first="Morgan" last="Chopin">Morgan Chopin</name><name sortKey="Chopin, Morgan" sort="Chopin, Morgan" uniqKey="Chopin M" first="Morgan" last="Chopin">Morgan Chopin</name></country><country name="Australie"><noRegion><name sortKey="Fellows, Michael R" sort="Fellows, Michael R" uniqKey="Fellows M" first="Michael R." last="Fellows">Michael R. Fellows</name></noRegion><name sortKey="Fellows, Michael R" sort="Fellows, Michael R" uniqKey="Fellows M" first="Michael R." last="Fellows">Michael R. Fellows</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006357 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006357 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:70BD68B8E1DA56DBB7F6C3404A53D5FD25290EE3
|texte= Parameterized Complexity of the Firefighter Problem
}}
| This area was generated with Dilib version V0.6.33. |  |